home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / utils / hash / hashfn.c < prev   
Encoding:
C/C++ Source or Header  |  1992-08-27  |  2.9 KB  |  154 lines
  1. /*
  2.  * hashfn.c
  3.  *
  4.  * Identification:
  5.  *    $Header: /private/postgres/src/utils/hash/RCS/hashfn.c,v 1.5 1992/03/30 00:07:41 mer Exp $
  6.  *
  7.  */
  8. #include "utils/hsearch.h"
  9.  
  10. /*
  11.     Assume that we've already split the bucket to which this
  12.     key hashes, calculate that bucket, and check that in fact
  13.     we did already split it.
  14. */
  15. int
  16. string_hash(key,keysize)
  17. char *    key;
  18. int    keysize;
  19. {
  20.     int h;
  21.     register unsigned char *k = (unsigned char *) key;
  22.  
  23.     h = 0;
  24.     /*
  25.      * Convert string to integer
  26.      */
  27.     while (*k)
  28.         h = h * PRIME1 ^ (*k++ - ' ');
  29.     h %= PRIME2;
  30.  
  31.     return (h);
  32. }
  33.  
  34.  
  35. tag_hash(key,keysize)
  36. int *    key;
  37. int    keysize;
  38. {
  39.     register int h = 0;
  40.  
  41.     /*
  42.      * Convert tag to integer;  Use four byte chunks in a "jump table"
  43.      * to go a little faster.  Currently the maximum keysize is 16
  44.      * (mar 17 1992) I have put in cases for up to 24.  Bigger than
  45.      * this will resort to the old behavior of the for loop. (see the
  46.      * default case).
  47.      */
  48.     switch (keysize)
  49.     {
  50.         case 6*sizeof(int):
  51.         h = h * PRIME1 ^ (*key);
  52.         key++;
  53.         /* fall through */
  54.  
  55.         case 5*sizeof(int):
  56.         h = h * PRIME1 ^ (*key);
  57.         key++;
  58.         /* fall through */
  59.  
  60.         case 4*sizeof(int):
  61.         h = h * PRIME1 ^ (*key);
  62.         key++;
  63.         /* fall through */
  64.  
  65.         case 3*sizeof(int):
  66.         h = h * PRIME1 ^ (*key);
  67.         key++;
  68.         /* fall through */
  69.  
  70.         case 2*sizeof(int):
  71.         h = h * PRIME1 ^ (*key);
  72.         key++;
  73.         /* fall through */
  74.  
  75.         case sizeof(int):
  76.         h = h * PRIME1 ^ (*key);
  77.         key++;
  78.         break;
  79.  
  80.         default:
  81.         for(; keysize > (sizeof(int)-1); keysize -= sizeof(int), key++)
  82.             h = h * PRIME1 ^ (*key);
  83.         /*
  84.          * now let's grab the last few bytes of the tag if the tag
  85.          * has (size % 4) != 0 (which it sometimes will on a sun3).
  86.          */
  87.         if (keysize)
  88.         {
  89.             char *keytmp = (char *)key;
  90.  
  91.             switch (keysize)
  92.             {
  93.             case 3:
  94.                 h = h * PRIME1 ^ (*keytmp);
  95.                 keytmp++;
  96.                 /* fall through */
  97.             case 2:
  98.                 h = h * PRIME1 ^ (*keytmp);
  99.                 keytmp++;
  100.                 /* fall through */
  101.             case 1:
  102.                 h = h * PRIME1 ^ (*keytmp);
  103.                 break;
  104.             }
  105.         }
  106.         break;
  107.     }
  108.  
  109.     h %= PRIME2;
  110.     return (h);
  111. }
  112.  
  113. /*
  114.  * This is INCREDIBLY ugly, but fast.
  115.  * We break the string up into 8 byte units.  On the first time
  116.  * through the loop we get the "leftover bytes" (strlen % 8).
  117.  * On every other iteration, we perform 8 HASHC's so we handle
  118.  * all 8 bytes.  Essentially, this saves us 7 cmp & branch
  119.  * instructions.  If this routine is heavily used enough, it's
  120.  * worth the ugly coding
  121.  */
  122. int
  123. disk_hash(key)
  124. char *key;
  125. {
  126.         register int n = 0;
  127.     register char *str = key;
  128.     register int len = strlen(key);
  129.     register int loop;
  130.  
  131. #define HASHC   n = *str++ + 65599 * n
  132.  
  133.         if (len > 0) {
  134.                 loop = (len + 8 - 1) >> 3;
  135.  
  136.                 switch(len & (8 - 1)) {
  137.             case 0: do {        /* All fall throughs */
  138.                     HASHC;  
  139.                 case 7: HASHC;
  140.                 case 6: HASHC;  
  141.                 case 5: HASHC;
  142.                 case 4: HASHC;  
  143.                 case 3: HASHC;
  144.                 case 2: HASHC;  
  145.                 case 1: HASHC;
  146.                         } while (--loop);
  147.                 }
  148.  
  149.         }
  150.     return(n);
  151. }
  152.  
  153.  
  154.